package com.my.algorithmlearning.leetcode;

import org.springframework.util.Assert;

/**
 * @ClassName Medium_62_UniquePaths
 * @Description 题解：https://leetcode.cn/problems/unique-paths/solution/zhong-deng-62-bu-tong-lu-jing-dong-tai-g-qhng/
 * @Author wanghaiwei
 * @Date 2023/3/2 14:45
 */
public class Medium_62_UniquePaths {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        int[][] history = new int[m][n];
        history[0][0] = 1;
        history[0][1] = 1;
        history[1][0] = 1;
        history[1][1] = 2;
        return dp(m - 1, n - 1, history);
    }

    private int dp(int mIdx, int nIndx, int[][] history) {
        if (mIdx == 0 || nIndx == 0) {
            return 1;
        }
        if (history[mIdx][nIndx] > 0) {
            return history[mIdx][nIndx];
        }
        history[mIdx - 1][nIndx] = dp(mIdx - 1, nIndx, history);
        history[mIdx][nIndx - 1] = dp(mIdx, nIndx - 1, history);
        return history[mIdx - 1][nIndx] + history[mIdx][nIndx - 1];
    }

    public static void main(String[] args) {
        Medium_62_UniquePaths solution = new Medium_62_UniquePaths();
        int result = solution.uniquePaths(3, 7);
        Assert.isTrue(28 == result, " m = 3, n = 7计算错误,预期：28，实际：" + result);

        result = solution.uniquePaths(3, 2);
        Assert.isTrue(3 == result, " m = 3, n = 2计算错误,预期：3，实际：" + result);
    }
}
